#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr){};
};

class Solution {
  public:
    TreeNode* buildTree(const vector<int>& preorder, const vector<int>& inorder) {
        TreeNode* root = helper(preorder, 0, preorder.size(), inorder, 0, inorder.size());
        return root;
    }

  private:
    TreeNode* helper(const vector<int>& preorder, int pstart, int pend, const vector<int>& inorder, int istart,
                     int iend) {
        // std::cout << pstart << ", " << pend << ", " << istart << ", " << iend << "\n";
        if (pend == pstart or iend == istart) return nullptr;
        auto root = new TreeNode(preorder[pstart]);
        int iroot_index = istart;
        for (; iroot_index < iend; ++iroot_index) {
            if (inorder[iroot_index] == preorder[pstart]) break;
        }
        int left_len = iroot_index - istart;
        root->left = helper(preorder, pstart + 1, pstart + 1 + left_len, inorder, istart, iroot_index);
        root->right = helper(preorder, pstart + 1 + left_len, pend, inorder, iroot_index + 1, iend);
        return root;
    }
};

int main() {
    std::vector<int> pre{3, 9, 20, 15, 7};
    std::vector<int> in{9, 3, 15, 20, 7};
    Solution s;
    s.buildTree(pre, in);
}
